package demo6;
import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class Solution {
    //两数之和 IV - 输入二叉搜索树
/*    private List<Integer> list = new LinkedList<>();
    public boolean findTarget(TreeNode root, int k) {
        //中序遍历==递增
        dfs(root);
        int len = list.size();
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < len; i++) {
            if(set.contains(k - list.get(i))) {
                return true;
            }
            set.add(list.get(i));
        }
        return false;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }*/
    //1.两数之和 IV - 输入二叉搜索树(dfs + 哈希表) + 优化
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if(root == null) {
            return false;
        }
        if(set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
    //2.二叉搜索树中的众数(中序遍历)
    private List<Integer> list = new ArrayList<>();//保存最大元素的
    private int max;//最大长度
    private int size;
    private int num;
    public int[] findMode(TreeNode root) {
        this.num = root.val;
        dfs(root);
        int len = list.size();
        int[] ret = new int[len];
        for(int i = 0; i < len; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        if(root.val == num) {
            size++;
        }else {//不等于size就重新开始计数
            size = 1;
            num = root.val;
        }
        if(size > max) {//大于最大长度，就清空list，并放入num
            max = size;
            list.clear();
            list.add(num);
        }else if(size == max) {
            list.add(num);
        }
        dfs(root.right);
    }
    //3.N 叉树的后序遍历(DFS)
    private List<Integer> list = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        dfs(root);
        return list;
    }
    private void dfs(Node root) {
        if(root == null) {
            return;
        }
        for(int i = 0; i < root.children.size(); i++) {
            postorder(root.children.get(i));
        }
        list.add(root.val);
    }
    //4.递增顺序搜索树(原树上修改)
    private TreeNode head;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode();//设置一个虚拟结点
        head = dummy;
        dfs(root);
        return dummy.right;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        head.right = root;
        root.left = null;
        head = root;
        dfs(root.right);
    }
    //5.叶子相似的树(dfs记录结点)
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        return list1.equals(list2);
    }
    private void dfs(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        dfs(root.left, list);
        dfs(root.right, list);
    }
    //6.单值二叉树(dfs)
    private int num = -1;
    public boolean isUnivalTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(num == -1) {
            num = root.val;
        }else if(num != root.val){
            return false;
        }
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }
    //7. 二叉树中第二小的节点(dfs)
    public int findSecondMinimumValue(TreeNode root) {
        //思路：可以将问题转化为求左右子树的最小值，若左右子树都小于根节点，取最小值
        return dfs(root, root.val);
    }
    private int dfs(TreeNode root, int rootVal) {
        if(root == null) {
            return -1;
        }
        if(root.val > rootVal) {
            return root.val;
        }
        int left = dfs(root.left, rootVal);
        int right = dfs(root.right, rootVal);
        if(left != -1 && right != -1) {
            return Math.min(left, right);
        }else {
            return Math.max(left, right);
        }
    }
    //8.二叉搜索树节点最小距离(dfs)
    private int prev = -1;//上一个结点的值
    private int min = Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
        dfs(root);
        return min;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        if(prev == -1) {
            prev = root.val;
        }else {
            int sum = Math.abs(prev - root.val);
            if(sum < min) {
                min = sum;
            }
            prev = root.val;
        }
        dfs(root.right);
    }
    //9.修剪二叉搜索树(dfs)
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) {
            return root;
        }
        if(root.val < low) {
            //左子树小于根节点的结点值，说明左树的左树一定小于，所以递归的去看左树的右树即可
            return trimBST(root.right, low, high);
        }
        if(root.val > high) {
            return trimBST(root.left, low, high);//和上面同理
        }
        //递归的去看左右子树
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
    //10.二叉树剪枝(dfs)
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.val == 0 && root.left == null && root.right == null) {
            return null;
        }
        return root;
    }
}
